package com.zrrd.aaa;

/**
 * @author WanJl
 * @version 1.0
 * @title BestTravel
 * @description
 * @create 2024/8/30
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BestTravel {

    public static int chooseBestSum(int t, int k, List<Integer> ls) {
        if (ls == null || ls.size() < k) {return 0;}
        List<Integer> combinations = new ArrayList<>();
        combine(ls, new ArrayList<>(), k, 0, combinations);
        int bestSum = 0;
        for (int sum : combinations) {
            if (sum <= t && sum > bestSum) {
                bestSum = sum;
            }
        }
        return bestSum;
    }
    private static void combine(List<Integer> ls, List<Integer> current, int k, int start, List<Integer> combinations) {
        if (current.size() == k) {
            int sum = current.stream().mapToInt(Integer::intValue).sum();
            combinations.add(sum);
            return;
        }
        for (int i = start; i < ls.size(); i++) {
            current.add(ls.get(i));
            combine(ls, current, k, i + 1, combinations);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] i1=new int[]{50,55, 56, 57, 58};
        List<Integer> ls1 = Arrays.asList(50, 55, 56, 57, 58);
        System.out.println(chooseBestSum(163, 3, ls1)); // 输出: 163

        List<Integer> ls2 = Arrays.asList(50);
        System.out.println(chooseBestSum(163, 3, ls2)); // 输出: 0

        List<Integer> ls3 = Arrays.asList(91, 74, 73, 85, 73, 81, 87);
        System.out.println(chooseBestSum(230, 3, ls3)); // 输出: 228
    }
}